class TreeNode {
    constructor(val, left, right) {
        this.val = val === undefined ? 0 : val
        this.left = left === undefined ? null : left
        this.right = right === undefined ? null : right
    }
}

class Node {
    constructor(val, left, right, next) {
        this.val = val === undefined ? null : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
        this.next = next === undefined ? null : next;
    }
};
/**
 *  二叉树
 * // 前序遍历 中节点 ---> 左节点 ---> 右节点
 * // 中序遍历 左节点 ---> 中节点 ---> 右节点
 * // 后序遍历 左节点 ---> 右节点 ---> 中节点
 */

class MyBinaryTree {
    constructor() {
        this._root = new TreeNode()
    }

    // 构建二叉树
    create (arr) {
        if (!arr.length) return
        //[3,9,20,null,null,15,7]
        this._root.val = arr[0]
        let stack = [this._root], index = 1, len = arr.length
        while (index < len) {
            let node = stack.shift()

            if (arr[index] !== null) {
                node.left = new TreeNode(arr[index])
                stack.push(node.left)
            }
            index++
            if (index < len && arr[index] !== null) {
                node.right = new TreeNode(arr[index])
                stack.push(node.right)
            }
            index++
        }
    }

    // 递归遍历 type = 1 前序,type = 2 中序,type = 3 后序
    traversal (type = 1) {
        const dfs = function (treeNode, ant) {
            if (!treeNode) return
            if (type == 1) ant.push(treeNode.val)
            dfs(treeNode.left, ant)
            if (type == 2) ant.push(treeNode.val)
            dfs(treeNode.right, ant)
            if (type == 3) ant.push(treeNode.val)
        }
        const datas = []
        dfs(this._root, datas)
        console.log(datas)
    }

    // 迭代法遍历
    iteration (type) {
        // 前序,后序
        const traversal1 = function (type = 1) {
            if (!this._root) return []
            let stack = [this._root], datas = []
            while (stack.length) {
                let node = stack.pop()
                datas.push(node.val)
                if (type == 1) {
                    if (node.right) datas.push(node.right)
                    if (node.left) datas.push(node.left)
                } else {
                    if (node.left) datas.push(node.left)
                    if (node.right) datas.push(node.right)
                }
            }
            return type == 1 ? datas : datas.reverse()
        }
        // 中序遍历
        const traversal2 = function () {
            let stack = [], cur = this._root, datas = []
            while (cur || stack.length) {
                if (cur) {
                    stack.push(cur.left)
                    cur = cur.left
                } else {
                    let node = stack.pop()
                    datas.push(node.val)
                    cur = node.right
                }
            }
            return datas
        }

        if (type == 2) return traversal2()
        else return traversal1(type)
    }

    // 层序遍历
    levelTraversal () {
        if (!this._root) return []
        let stack = [this._root], datas = []
        while (stack.length) {
            let node = stack.shift()
            datas.push(node.val)
            if (node.left) stack.push(node.left)
            if (node.right) stack.push(node.right)
        }
        return datas
    }

    // 翻转
    reverse () {
        // 方法一 递归
        // const dfs = function (treeNode) {
        //     if (!treeNode) return null
        //     const left = dfs(treeNode.left)
        //     const right = dfs(treeNode.right)
        //     treeNode.left = right
        //     treeNode.right = left
        //     return treeNode
        // }
        // dfs(this._root)

        // 方法二 堆栈
        let stack = [this._root]
        while (stack.length) {
            const node = stack.shift()
            let temp = node.left
            node.left = node.right
            node.right = temp
            if (node.left) stack.push(node.left)
            if (node.right) stack.push(node.right)
        }
        console.log(this._root)
    }

    // 获取最大高度
    getMaxHeight () {
        // 递归法
        // const dfs = function (treeNode) {
        //     debugger
        //     if (!treeNode) return 0
        //     // const left = dfs(treeNode.left)
        //     // const right = dfs(treeNode.right)
        //     return Math.max(dfs(treeNode.left), dfs(treeNode.right)) + 1
        // }
        // let max = dfs(this._root)

        // 迭代法
        let stack = [this._root], count = 0, max = 0
        while (stack.length) {
            debugger
            let lastNode = stack[stack.length - 1]
            if (lastNode) {
                stack.push(null)
                count++
                lastNode.right && stack.push(lastNode.right)
                lastNode.left && stack.push(lastNode.left)
            } else {
                stack.pop()
                stack.pop()
                count--
            }
            max = Math.max(max, count)
        }
        return max
    }

    // 获取最小深度  //最小深度是从根节点到最近叶子节点的最短路径上的节点数量
    getMinHeight (root) {
        if (!root) return 0
        if (!root.left && root.right) return this.getMinHeight(root.right) + 1
        else if (root.left && !root.right) return this.getMinHeight(root.left) + 1
        else return Math.min(this.getMinHeight(root.left), this.getMinHeight(root.right)) + 1
    }

    // 是否为平衡二叉树,(当前节点的左右节点深度相处不超过1)
    isBalanced () {
        // 递归法
        const dfs = function (treeNode) {
            debugger
            if (!treeNode) return 0
            const left = dfs(treeNode.left)
            const right = dfs(treeNode.right)
            if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1
            else return Math.max(left, right) + 1
        }
        const res = dfs(this._root)
    }

    // 从前序与中序遍历序列构造二叉树(元素不重复)
    buildTreeFromPre (preorder, inorder) {
        debugger
        if (preorder.length) return null
        let index = inorder.indexOf(preorder[0]),
            preLeft = preorder.slice(1, index + 1),
            preRight = preorder.slice(index + 1),
            inLeft = inorder.slice(0, index),
            inRight = inorder.slice(index + 1),
            left = this.buildTreeFromPre(preLeft, inLeft),
            right = this.buildTreeFromPre(preRight, inRight);

        return new TreeNode(preorder[0], left, right)
    }

    // 从中序与后序遍历序列构造二叉树(元素不重复)
    buildTreeFromPost (inorder, postorder) {
        debugger
        let n = postorder.length
        if (!n) return null

        let val = postorder[n - 1],
            index = inorder.indexOf(val),
            inLeft = inorder.slice(0, index), // 中序获取左子节点
            inRight = inorder.slice(index + 1),  //中序获取右子节点
            leftLen = inLeft.length,
            postLeft = postorder.slice(0, leftLen),
            postRight = postorder.slice(leftLen, n - 1),
            left = this.buildTreeFromPost(inLeft, postLeft),
            right = this.buildTreeFromPost(inRight, postRight);
        return new TreeNode(val, left, right)
    }

    // 从前序和后序遍历构造二叉树(元素不重复)
    constructFromPrePost (preorder, postorder) {
        if (!preorder.length) return null
        let root = new TreeNode(preorder[0])
        if (preorder.length == 1) return root
        let leftPost = [], rightPost = [], leftPre = [], rightPre = [];
        let index = postorder.indexOf(preorder[1]);
        // 只存在左右节点其中的一个
        if (index + 1 == postorder.length - 1) {
            if (preorder[1] === postorder[0]) {
                // 右节点为空
                leftPost = postorder.slice(0, index + 1)
                leftPre = preorder.slice(1)
            } else {
                // 左节点为空
                rightPost = postorder.slice(0, index + 1)
                rightPre = preorder.slice(1)
            }
        } else {
            // 同时存在左右节点
            leftPost = postorder.slice(0, index + 1)
            rightPost = postorder.slice(index + 1, postorder.length - 1)
            leftPre = preorder.slice(1, leftPost.length + 1)
            rightPre = preorder.slice(leftPost.length + 1)
        }

        root.left = constructFromPrePost(leftPre, leftPost)
        root.right = constructFromPrePost(rightPre, rightPost)

        return root
    }

    //合并二叉树
    mergeTrees (root1, root2) {
        // 迭代法
        // const method1 = function () {
        //     if (!root1) return root2
        //     if (!root2) return root1
        //     root1.val += root2.val
        //     let stack = [root1, root2]
        //     while (stack.length) {
        //         let node = stack.shift(),
        //             node2 = stack.shift()
        //         if (node2.left) {
        //             if (!node.left) node.left = node2.left
        //             else {
        //                 // 左右节点都存在的情况下才进行下次合并对比
        //                 node.left.val += node2.left.val
        //                 stack.push(node.left, node2.left)
        //             }
        //         }

        //         if (node2.right) {
        //             if (!node.right) node.right = node2.right
        //             else {
        //                 // 左右节点都存在的情况下才进行下次合并对比
        //                 node.right.val += node2.right.val
        //                 stack.push(node.right, node2.right)
        //             }
        //         }
        //     }
        //     return root1
        // }

        debugger
        // 递归法
        if (!root1) return root2
        if (!root2) return root1
        const left = this.mergeTrees(root1.left, root2.left)
        const right = this.mergeTrees(root1.right, root2.right)

        root1.val += root2.val
        root1.left = left
        root1.right = right
        return root1
    }

    // 222.获取节点个数
    countNodes () {
        // const dfs = function (root) {
        //     if (!root) return 0
        //     return dfs(root.left) + dfs(root.right) + 1
        // }
        // console.log(dfs(this._root))

        //在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，
        //并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2 ^ (h - 1)  个节点。
        const dfs = function (root) {
            debugger
            if (!root) return 0
            let left = root.left, right = root.right, leftDepth = 0, rightDepth = 0;
            while (left) {
                leftDepth++
                left = left.left
            }
            while (right) {
                rightDepth++
                right = right.right
            }
            if (leftDepth == rightDepth) {
                return (2 << leftDepth) - 1
            }

            return dfs(root.left) + dfs(root.right) + 1
        }
    }

    // 257.二叉树的所有路径
    binaryTreePaths () {
        let ant = []
        const dfs = function (root, path) {
            debugger
            if (!root) {
                return
            }
            path += root.val.toString();
            if (!root.left && !root.right) {
                ant.push(path)
            } else {
                path += '->'
                dfs(root.left, path)
                dfs(root.right, path)
            }
        }
        dfs(this._root, '')
        console.log(ant)
    }

    // 543.二叉树的直径
    diameterOfBinaryTree () {
        let max = 0
        const countNodes = function (treeNode) {
            if (!treeNode) return 0
            let left = countNodes(treeNode.left)
            let right = countNodes(treeNode.right)
            max = Math.max(left + right, max)
            return Math.max(left, right) + 1
        }
        countNodes(this._root)
        return max
    }

    //563. 二叉树的坡度
    findTilt () {
        let sum = 0
        const dfs = function (treeNode) {
            if (!treeNode) return 0
            const left = dfs(treeNode.left),
                right = dfs(treeNode.right);
            sum += Math.abs(left - right)
            return left + right + treeNode.val
        }
        dfs(this._root)
        return sum
    }

    //993.二叉树的堂兄弟节点
    isCousins (root, x, y) {
        let d = 0, d1 = 0, d2 = 0, stack = [root]
        while (stack.length) {
            debugger
            let size = stack.length
            d++
            while (size--) {
                let node = stack.shift()
                if (node.left && node.right) {
                    if (node.left.val == x && node.right.val == y) return false
                    if (node.left.val == y && node.right.val == x) return false
                }
                if (node.val == x) d1 = d
                else if (node.val == y) d2 = d
                else {
                    if (node.left) stack.push(node.left)
                    if (node.right) stack.push(node.right)
                }
            }
            if (d1 != d2) return false
        }

        return d1 && d2 && d1 == d2
    }

    // 655.输出二叉树 (输出一个二维数组)
    printTree (root) {
        //[1,2,3,null,4]
        //[["","","","1","","",""],
        //["","2","","","","3",""],
        //["","","4","","","",""]],
        const getHeight = function (treeNode) {
            if (!treeNode) return 0
            return Math.max(getHeight(treeNode.left), getHeight(treeNode.right)) + 1
        }

        let height = getHeight(root) - 1,
            m = height + 1,
            n = (1 << m) - 1,
            ant = new Array(m).fill(0).map(_ => Array(n).fill(''))

        const dfs = function (root, r, c, res) {
            res[r][c] = root.val.toString()
            if (root.left) {
                dfs(root.left, r + 1, c - (1 << height - r - 1), res)
            }
            if (root.right) {
                dfs(root.right, r + 1, c + (1 << height - r - 1), res)
            }
        }

        dfs(root, 0, n >> 1, ant)

    }

    // 1028.从先序遍历还原二叉树
    recoverFromPreorder (traversal) {
        const len = traversal.length;
        let stack = []
        for (let i = 0; i < len;) {
            debugger
            let level = 0
            while (i < len && traversal[i] == '-') {
                level++
                i++
            }
            let start = i
            while (i < len && traversal[i] !== '-') {
                i++
            }
            let val = traversal.substring(start, i)
            let treeNode = new TreeNode(val)
            if (!stack.length) {
                stack.push(treeNode)
                continue
            }
            while (stack.length > level) {
                stack.pop()
            }
            let parent = stack[stack.length - 1]
            if (parent.left) parent.right = treeNode
            else parent.left = treeNode

            stack.push(treeNode)
        }
    }

    // 114.二叉树展开为链表,修改原链表
    flatten (root) {
        if (!root) return null

        let stack = [root.right, root.left], cur = root

        while (stack.length) {
            let node = stack.pop()
            if (!node) continue
            if (node.right) stack.push(node.right)
            if (node.left) stack.push(node.left)
            cur.left = null
            cur.right = node
            cur = cur.right
        }
    };

    // 236.二叉树的最近公共祖先
    lowestCommonAncestor (root, p, q) {
        let t1 = [], t2 = []
        const dfs = function (treeNode, path) {
            if (!treeNode) return null
            path.push(treeNode)

            if (treeNode.val == p.val) t1 = [...path]
            if (treeNode.val == q.val) t2 = [...path]

            if (t1.length && t2.length) {
                let res = []
                for (let i in t1) {
                    if (t1[i] && t2[i] && t1[i].val == t2[i].val) res = t1[i]
                    else break
                }
                return res
            }

            let left = dfs(treeNode.left, path)
            if (left) return left
            else {
                let right = dfs(treeNode.right, path)
                path.pop()
                if (right) return right
            }
        }

        dfs(root, [], false, false)
    }

    //序列化前序遍历 297.二叉树的序列化与反序列化
    serialize () {
        const dfs = function (treeNode, i, path) {
            if (!treeNode) return path
            path += '/'.repeat(i) + treeNode.val
            i++
            let left = dfs(treeNode.left, i, path)
            // 标记当前节点的左节点为空的情况
            if (!treeNode.left && treeNode.right) {
                left += '/'.repeat(i) + null
            }
            // 将左节点的路径传入右节点,拼接节点路径
            const right = dfs(treeNode.right, i, left)
            return right
        }
        return dfs(this._root, 0, '')
    }

    //反序列化 297.二叉树的序列化与反序列化
    deserialize (data) {
        const stack = [], len = data.length
        for (let i = 0; i < len;) {
            let level = 0
            while (i < len && data[i] == '/') {
                level++
                i++
            }
            let start = i
            while (i < len && data[i] !== '/') i++
            let val = data.substring(start, i)
            let node = new TreeNode(val)
            if (!stack.length) {
                stack.push(node)
                continue
            }
            while (stack.length > level) stack.pop()

            const last = stack[stack.length - 1]

            if (last.left) {
                last.right = node
                // 重置左节点为空
                if (last.left.val == 'null') last.left = null
            } else {
                last.left = node
            }
            if (val != 'null') stack.push(node)
        }
        return stack[0]
    }

    //987. 二叉树的垂序遍历
    verticalTraversal () {
        const h = {}

        const dfs = function (treeNode, i, flag, level) {
            // debugger
            if (!treeNode) return
            i += flag
            if (h[i]) {
                if (h[i][level]) {
                    h[i][level].push(treeNode.val)
                    h[i][level].sort((a, b) => a - b)
                }
                else h[i][level] = [treeNode.val]
            }
            else {
                h[i] = {}
                h[i][level] = [treeNode.val]
            }
            level++
            dfs(treeNode.left, i, -1, level)
            dfs(treeNode.right, i, 1, level)
        }

        dfs(this._root, 1001, 0, 0)

        const ant = []

        for (let k in h) {
            let res = []
            for (let j in h[k]) {
                res.push(...h[k][j])
            }
            ant.push(res)
        }
        debugger
        console.log(ant)
    }

    //1367.二叉树中的链表
    isSubPath () {
        let cur = head, link = ''
        while (cur) {
            link += cur.val + ','
            cur = cur.next
        }
        const dfs = function (treeNode, path) {
            if (!treeNode) return false
            path += treeNode.val + ','
            if (path.includes(link)) return true
            let left = dfs(treeNode.left, path),
                right = dfs(treeNode.right, path)
            return left || right

        }
        return dfs(this._root, '')
    }

    // 662.二叉树最大宽度
    widthOfBinaryTree () {
        let max = 1, stack = [[root, 1]]
        while (stack.length) {
            max = Math.max(stack[stack.length - 1][1] - stack[0][1] + 1, max)
            let temp = []
            for (let [node, index] of stack) {
                node.left && temp.push([node.left, index * 2])
                node.right && temp.push([node.right, index * 2 + 1])
            }
            if (stack[0][1] > 1 << 31) {
                temp.forEach(item => item[1] -= stack[0][1])
            }
            stack = temp
        }
        return max
    }

    // 124.二叉树中的最大路径和
    maxPathSum () {
        let max = Number.MIN_SAFE_INTEGER
        const dfs = function (treeNode) {
            debugger
            if (!treeNode) return 0
            const left = dfs(treeNode.left)
            const right = dfs(treeNode.right)
            let sum = treeNode.val
            if (left > 0) sum += left
            if (right > 0) sum += right
            max = Math.max(sum, max)
            return Math.max(left + treeNode.val, right + treeNode.val, treeNode.val)
        }

        dfs(this._root)
        return max
    }

    //623.在二叉树中增加一行
    addOneRow (root, val, depth) {
        debugger
        if (depth == 1) return new TreeNode(val, root)
        let pre = null, cur = [root]
        while (--depth) {

            let temp = []
            for (let node of cur) {
                node.left && temp.push(node.left)
                node.right && temp.push(node.right)
            }
            pre = cur
            cur = temp
        }

        for (let node of pre) {
            let left = node.left, right = node.right
            node.left = new TreeNode(val, left)
            node.right = new TreeNode(val, null, right)
        }
        return root
    }

    //814.二叉树剪枝
    pruneTree () {
        const dfs = function (treeNode) {
            debugger
            if (!treeNode) return null
            let left = dfs(treeNode.left)
            let right = dfs(treeNode.right)
            if (!left && !right && !treeNode.val) return null
            treeNode.left = left
            treeNode.right = right
            return treeNode

        }

        dfs(this._root)
    }

    //2641.二叉树的堂兄弟节点 II
    replaceValueInTree () {
        // [5, 4, 9, 1, 10, null, 7, 6, null, 5, 4]
        // stack: [[1,10],[7]],curSum=[11,7],curTotalSum = 18
        let stack = [[this._root]], curSum = [0], curTotalSum = 0
        while (stack.length) {
            let temp = [], sum = [], allSum = 0
            for (let i = 0; i < stack.length; i++) {
                let nodes = stack[i], curVal = curTotalSum - curSum[i]
                for (let node of nodes) {
                    node.val = curVal
                    let ant = [], val = 0
                    node.left && ant.push(node.left) && (val += node.left.val)
                    node.right && ant.push(node.right) && (val += node.right.val)
                    ant.length && temp.push(ant) && sum.push(val)
                    allSum += val
                }
            }
            stack = temp
            curSum = sum
            curTotalSum = allSum
        }
    }

    // 2673.使二叉树所有路径值相等的最小代价
    minIncrements (n, cost) {
        let ant = 0
        for (let i = n - 2; i > 0; i -= 2) {
            debugger
            ant += Math.abs(cost[i] - cost[i + 1])
            count[i >> 1] += Math.max(cost[i], cost[i - 1])
        }

        return ant
    }

    // 113.路径总和 II
    pathSum (targetSum) {
        let ant = []
        const dfs = function (treeNode, sum, path) {
            debugger
            if (!treeNode) return
            path.push(treeNode.val)
            sum += treeNode.val
            if (!treeNode.left && !treeNode.right) {
                if (sum == targetSum) ant.push([...path])
                path.pop()
                return
            }
            dfs(treeNode.left, sum, path)
            dfs(treeNode.right, sum, path)
            path.pop()
        }

        dfs(this._root, 0, [])

        return ant
    }

    lowestCommonAncestor (root, p, q) {
        debugger
        if (!root) return null

        if ((root.val > p.val && root.val < q.val)
            || (root.val > q.val && root.val < p.val)
            || (root.val == q.val)
            || (root.val == p.val)
        ) return root

        return this.lowestCommonAncestor(root.left) || this.lowestCommonAncestor(root.right)
    }

    //二叉搜索数的序列化
    serializeSearchTree () {
        if (!this._root) return ''
        let arr = []
        const dfs = function (treeNode) {
            if (!treeNode) return
            dfs(treeNode.left)
            dfs(treeNode.right)
            arr.push(treeNode.val)
        }
        dfs(this._root)
        return arr.join(',')
    }

    //二叉搜索数的反序列化
    deserializeSearchTree (data) {
        if (!data) return null
        let stack = data.split(',')

        const dfs = function (low, upper) {
            debugger
            if (!stack.length || stack[stack.length - 1] < low || stack[stack.length - 1] > upper) {
                return null
            }
            let val = Number(stack.pop())
            let root = new TreeNode(val)
            root.right = dfs(val, upper)
            root.left = dfs(low, val)
            return root
        }

        return dfs(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
    }


    // 删除二叉搜索树中的节点
    deleteNode (root, key) {
        if (!root) return null
        // 目标值 < 当前节点值时,在左节点查找目标值
        if (root.val > key) {
            root.left = this.deleteNode(root.left, key)
            return root
            // 目标值 > 当前节点值时,在右节点查找目标值
        } else if (root.val < key) {
            root.right = this.deleteNode(root.right, key)
            return root
        } else {
            // 左右节点不存在
            if (!root.left && !root.right) return null
            // 左节点不存在
            else if (root.left && !root.right) return root.left
            // 右节点不存在
            else if (!root.left && root.right) return root.right
            // 左右节点同时都存在,找出左侧节点的最大值,将右节点添加到左侧节点
            else {
                let cur = root.left
                while (cur && cur.right) {
                    cur = cur.right
                }
                cur.right = root.right
                return root.left
            }
        }
    }

    // 二叉搜索树的范围和
    rangeSumBST (root, low, high) {
        let sum = 0
        const dfs = function (root) {
            debugger
            if (!root) return
            if (root.val >= low && root.val <= high) {
                sum += root.val
                dfs(root.left)
                dfs(root.right)
            } else if (root.val < low) {
                dfs(root.right)
            } else if (root.val > high) {
                dfs(root.left)
            }

        }

        dfs(root)
        return sum
    }

}

const myTrees = new MyBinaryTree()
let arr = [10, 5, 15, 3, 7, null, 18]
// let arr = [4, 2, 7, 1, 3, 6, 8, null, 1.2, null, null, 5, null, null, 9]
// 前序遍历 [1, 2, 4, 6, 8, 7, 5, 3, 9]   中序遍历[6, 8, 4, 7, 2, 5, 1, 3, 9]
myTrees.create(arr)
// // debugger
// console.log(myTrees.traversal(2))
// console.log(myTrees.traversal(3))

// const myTrees2 = new MyBinaryTree()
// myTrees2.create(arr2)

debugger
//"1-2--3--4-5--6--7"    //"1-2--3---4-5--6---7"   //"1-401--349--90---88"
myTrees.rangeSumBST(myTrees._root, 7, 15)